#include <assert.h>
#include <stdlib.h>
#include <string.h>
#include "const_prpgt.h"
#include "semantic.h"
#include "inter_code.h"
#include "error.h"
#include "sym_table.h"
#include "gp_list.h"
#include "list.h"
#include "dfg.h"


//#define CONST_PRPGT_DEBUG
#define ALGEBRA_SIMPLIFY_OUTPUT
#define COND_JMP_OPTIMIZE_OUTPUT

#define IS_CONST(val)       ((val != NAC) && (val != UNDEF))
#define NOT_CONST(val)      ((val == NAC) || (val == UNDEF))


void print_set_value(double *val, int count);

void kill_cond_jmp(bb_t *bb, struct list_head *head);


void __alloc_inst_in_out_set(struct list_head *head, int count)
{
	inter_inst_t *inst;
	// 为指令分配内存
	list_for_each_entry(inst, head, entry){
		inst->in_set = calloc(count, sizeof(double));
		if(!inst->in_set) {
			SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
			return;
		}
		inst->out_set = calloc(count, sizeof(double));
		if(!inst->out_set) {
			SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
			return;
		}
	} 
}

void __alloc_bb_in_out_set(struct list_head *head, int count)
{
	if(!head || !count)
		return;
	// 为流图中的基本块分配 in_set 和 out_set 的内存
	bb_t *cur_bb;
	list_for_each_entry(cur_bb, head, entry_in_dfg) {
		cur_bb->const_prpgt.cnt = count;
		cur_bb->const_prpgt.in_set = calloc(count, sizeof(double));
		if(!cur_bb->const_prpgt.in_set) {
			SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
			return;
		}
		cur_bb->const_prpgt.out_set = calloc(count, sizeof(double));
		if(!cur_bb->const_prpgt.in_set) {
			SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
			return;
		}
	}
}


void __set_bound_init_val(const_prpgt_info_t *const_prpgt, fun_t *fun)
{
  	int idx = 0; 
	int glb_vars_cnt = get_all_glb_vars();
	if(glb_vars_cnt){
		gp_node_t *cur;
		var_t *var;
		list_for_each_entry(cur, &glb_vars_head, entry) {
			var = (var_t *)cur->addr;
			var->optimize_id = idx; // 编号
			const_prpgt->var_info[idx] = var;
			double val = 0; // 生成汇编代码的时候，全局变量赋值为 0
			if(NOT_BASE(var)) // 非基本类型
				val = NAC; // not a const				
			else if(var->init_by_constant) // 使用常量初始化且是基本类型
				val= var->int_val; 
			const_prpgt->bound_vals[idx] = val; // 添加边界值			
			++idx;	
		}
	}

	if(fun->para_len){
		gp_node_t *node;
		list_for_each_entry(node, fun->para_list_head, entry){
            var_t *para = node->addr;
			const_prpgt->var_info[idx] = para;
			para->optimize_id = idx;
			const_prpgt->bound_vals[idx] = NAC;
			++idx;		
		}
	}
	
	if(fun->local_vars_cnt){
		inter_inst_t *inst;
		var_t *lcl_var;
		list_for_each_entry(inst, &fun->inter_code, entry) {
			if(inst->op == IR_OP_DECL) {
				lcl_var = inst->arg1;
				lcl_var->optimize_id = idx;
				const_prpgt->var_info[idx] = lcl_var;
				double val = UNDEF; // 默认变量都是 UNDEF
				if(NOT_BASE(lcl_var)) // 非基本类型
					val = NAC;				
				else if(lcl_var->init_by_constant) // 使用常量初始化
					val= lcl_var->int_val; 
				const_prpgt->bound_vals[idx] = val; // 添加边界值		
				++idx;
			}
		}
	}

	int j = 0;
	while(j < idx) {
		const_prpgt->init_vals[j++] = UNDEF; // 初始值全部是 UNDEF
	}
}
/*
	分配初始值和边界值
*/
const_prpgt_info_t *const_prpgt_init(fun_t *fun)
{
    if(!fun)
        return NULL;
	// 确定数组大小
	int glb_vars_cnt = get_all_glb_vars();
	int count = glb_vars_cnt + 
			fun->local_vars_cnt + fun->para_len;
	if(!count)
		return NULL;

	assert(fun->dfg);
	const_prpgt_info_t *cst_prpgt = 
			calloc(1, sizeof(const_prpgt_info_t));
	if(!cst_prpgt){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return NULL;
	}
	cst_prpgt->cnt = count;
	cst_prpgt->dfg = fun->dfg;
	cst_prpgt->inter_code = &fun->inter_code;
	INIT_LIST_HEAD(&cst_prpgt->optimized_code);
	__alloc_bb_in_out_set(&fun->dfg->bbs_head, count);
	__alloc_inst_in_out_set(cst_prpgt->inter_code, count);

    // 分配变量地址的内存,为了调试
	cst_prpgt->var_info = calloc(1, sizeof(var_t *) * count);
	if(!cst_prpgt->var_info){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return NULL;
	}	
    // 分配边界值数组的内存
	cst_prpgt->bound_vals = calloc(1, sizeof(double) * count);
	if(!cst_prpgt->bound_vals){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return NULL;
	}
    // 分配初始值数组的内存
	cst_prpgt->init_vals = calloc(1, sizeof(double) * count);
	if(!cst_prpgt->init_vals){
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return NULL;
	}
	__set_bound_init_val(cst_prpgt, fun);

#ifdef CONST_PRPGT_DEBUG
  	print_set_value(cst_prpgt->bound_vals, count);
	print_set_value(cst_prpgt->init_vals, count);
#endif
	return cst_prpgt;
}


void const_prpgt_destroy(const_prpgt_info_t *cst_prpgt)
{
	if(!cst_prpgt)
		return;
	struct list_head *head = &cst_prpgt->dfg->bbs_head;
	bb_t *cur_bb;
	list_for_each_entry(cur_bb, head, entry_in_dfg) {
		free(cur_bb->const_prpgt.in_set); 
		free(cur_bb->const_prpgt.out_set);
	} 	

	// 因为条件跳转优化中可能把指令从所在基本块删除，所以这里不是遍历基本块，
	// 而是遍历中间指令的链表
	inter_inst_t *inst;
	list_for_each_entry(inst, cst_prpgt->inter_code, entry){
		free(inst->in_set);
		free(inst->out_set);
	}		
	gp_list_free(&cst_prpgt->optimized_code);
	free(cst_prpgt->bound_vals);
	free(cst_prpgt->init_vals);
	free(cst_prpgt->var_info);
	free(cst_prpgt);
}

/*
	元素交汇运算规则
	龙书 P405
*/
double element_join(double left, double right)
{
	if(left == NAC || right == NAC)
		return NAC; // 与 NAC 交并结果必是 NAC
	else if(left == UNDEF)
		return right;  // 与 UNDEF 交并结果不变
	else if(right == UNDEF)
		return left;   // 与 UNDEF 交并结果不变
	else if(left == right)
		return left; // 同值元素交并结果相同
	else 
		return NAC; // 异值元素交并结果是 NAC
}

double get_lattice(var_t *var, double *set)
{
	assert(var && set);
	if(var->is_literal) {
		if(IS_BASE(var))
			return var->int_val;
		else 
			return NAC;
	} else {
		return set[var->optimize_id];
	}
}

void __inst_translate(inter_inst_t *inst, double *in, double *out, int count)
{
	operator_e op = inst->op;
	// 排除的指令：
	// IR_OP_DECL, IR_OP_FUN_ENTRY, IR_OP_FUN_EXIT,IR_OP_LEA
	// 各种跳转, IR_OP_RET, IR_OP_RET_VAL
	if((op < IR_OP_ASSIGN) || (op >= IR_OP_LEA && op <= IR_OP_JNE) || (op >= IR_OP_RET))
		return;
	
	var_t *result = inst->result;
	var_t *arg1 = inst->arg1;
	var_t *arg2 = inst->arg2;
	int glb_cnt = get_all_glb_vars();
	double tmp; // 存储临时值结果
	// 一元操作符
	if(op == IR_OP_ASSIGN || op == IR_OP_NOT || op == IR_OP_NEG) {
		tmp = get_lattice(arg1, in); 
		if(IS_CONST(tmp)) { // 处理常量
			if(op == IR_OP_NEG)
				tmp = -tmp;  // 直接计算
			else if(op == IR_OP_NOT)
				tmp = !tmp;  // 直接计算
		}
		out[result->optimize_id] = tmp; // 更新 out 集合值
		return;
	}

	if(op == IR_OP_ARG) {
		if(NOT_BASE(arg1)) {
			// 参数是非基本类型，破坏！！！ 
			for(int i = 0; i < count; ++i)
				out[i] = NAC; // 全部置为 NAC
			return;
		} else
			return;
	}

	if(op == IR_OP_STORE){
		// *arg1 = result 
		// 因为不知道指针指向哪里，保守估计全部修改
		for(int i = 0; i < count; ++i)
			out[i] = NAC; // 全部置为 NAC
		return;
	}

	if(op == IR_OP_LOAD) {
		// 破坏运算 result = *arg1
		out[result->optimize_id] = NAC; 
		return;
	}

	if(op == IR_OP_PROC) { 
		// 保守估计修改了全局变量
		for(int i = 0; i < glb_cnt; ++i)
			out[i] = NAC; // 全局变量全部置为 NAC, 全部变量在数组的最前面
		return;
	}

	if(op == IR_OP_CALL){
		// 保守估计修改了全局变量
		for(int i = 0; i < glb_cnt; ++i)
			out[i] = NAC; // 全局变量全部置为NAC, 全部变量在数组的最前面		
		out[result->optimize_id] = NAC;//函数返回值失去常量性质！——保守预测
		return;
	}

	// 二元运算
	double left = get_lattice(arg1, in);
	double right = get_lattice(arg2, in);

	if(left == NAC || right == NAC) {
		// 有一个 NAC,结果必是 NAC
		tmp = NAC; 
	} else if(left == UNDEF || right == UNDEF) { 
		// 都不是 NAC，有一个是 UNDEF，结果必是 UNDEF
		tmp = UNDEF;
	} else { // 都是 const
		int lop = (int)left;  // 类型转换
        int rop = (int)right; // 类型转换
		switch(op) {
			case IR_OP_ADD:
				tmp = lop + rop;
				break;

			case IR_OP_SUB:
				tmp = lop - rop;
				break;

			case IR_OP_MUL:
				tmp = lop * rop;
				break;

			case IR_OP_DIV:
				if(!rop)
                    tmp = NAC; // 除数为 0,特殊处理
                else 
                    tmp = lop / rop; 
				break;

			case IR_OP_MOD:
                if(!rop) 
                    tmp = NAC; // 除数为 0,特殊处理
                else 
                    tmp = lop % rop; 		
				break;

			case IR_OP_GT:
				tmp = lop > rop;
				break;

			case IR_OP_GE:
				tmp = lop >= rop;
				break;

			case IR_OP_LT:
				tmp = lop < rop;
				break;
			
			case IR_OP_LE:
				tmp = lop <= rop;
				break;
			
			case IR_OP_EQU:
				tmp = (lop == rop);
				break;
			case IR_OP_NEQU:
				tmp = (lop != rop);
				break;

			case IR_OP_AND:
				tmp = lop && rop;
				break;
			case IR_OP_OR:
				tmp = lop || rop;
				break;
			default:
				break;
		}
	}
	out[result->optimize_id] = tmp; // 更新 out 集合值
}

void inst_translate(inter_inst_t *inst, double *in, double *out, int count)
{
	assert(inst && in && out && count);
	memcpy(out, in, sizeof(double) * count); // 先拷贝过去，后面再处理特殊情况
	__inst_translate(inst, in, out, count);

	// 拷贝信息指令的in，out信息，方便代数化简，条件跳转优化和不可达代码消除
	memcpy(inst->in_set, in, sizeof(double) * count); 
	memcpy(inst->out_set, out, sizeof(double) * count); 
}



void print_lattice(double val)
{
	if(val == NAC)
	//	printf("⊥");
		printf("N");
	else if(val == UNDEF)
	//	printf("⊤"); 
		printf("U");
	else 
		printf("%d", (int)val);
}


void print_set_value(double *val, int count)
{
	for(int i = 0; i < count; ++i) {
		print_lattice(val[i]);
		printf(", ");
	}
	printf("\n");
}




// 收集每个前驱的 out, 交汇得到当前 block 的 in
void block_join(bb_t *block)
{
	if(list_empty(&block->prede_head)) // 没有前驱
		return;

	gp_node_t *pos;
	bb_t *bb;
	// 处理集合的每个元素
	for(int i = 0; i < block->const_prpgt.cnt; ++i){ 
		// 记录交并结果；因为任何元素和 UNDEF 交并都是它本身，
		// 所以这个初始化是合适的
		double val = UNDEF; 

		list_for_each_entry(pos, &block->prede_head, entry){
			bb = (bb_t *)pos->addr;
			val = element_join(val, bb->const_prpgt.out_set[i]);
		}
		block->const_prpgt.in_set[i] = val;
	}
}


int block_translate(bb_t *block) 
{
#ifdef CONST_PRPGT_DEBUG	
	printf("block id: %d\n", block->id);
	printf("IN: ");
	print_set_value(block->const_prpgt.in_set, block->const_prpgt.cnt);
#endif
	int size = block->const_prpgt.cnt * sizeof(double);
	double *in = malloc(size); 	
	if(!in) {
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return false;
	}
	double *out = malloc(size); 	
	if(!out) {
		free(in);
		SYSTEM_FATAL_ERR(MEM_ALLOC_FAILED);
		return false;
	}

	memcpy(in, block->const_prpgt.in_set, size); 
	memcpy(out, in, size); // 默认没有指令，直接传递； 
	
	inter_inst_t *inst;
	list_for_each_entry(inst, &block->insts_head, entry_in_bb){
		inst_translate(inst, in, out, block->const_prpgt.cnt);
		memcpy(in, out, size); // 当前指令的 out 传递给下一条指令的 in
	}
#ifdef CONST_PRPGT_DEBUG
	printf("OUT:");
	print_set_value(out, block->const_prpgt.cnt);
#endif
	int change = 0;
	/*
	因为一个块的输出也是它后继的输入，输出没有变化，说明输入也没有变化。
	当所有块的输出输入都没有变化，说明到了不动点。
	*/
	for(int i = 0; i < block->const_prpgt.cnt; ++i){
		if(block->const_prpgt.out_set[i] != out[i]){
#ifdef CONST_PRPGT_DEBUG
			printf("[%d] changed: " , i);
			print_lattice(block->const_prpgt.out_set[i]);
			printf(" => ");
			print_lattice(out[i]);
			printf("\n");
#endif
			change = 1; // 检测到变化
			// break;
		}
	}
	memcpy(block->const_prpgt.out_set, out, size);
	free(in);
	free(out);
	return change;
}




void add_block_to_worklist(bb_t *bb, struct list_head *worklist)
{
	assert(bb && worklist);
	// printf("add %d to list\n", bb->id);
	gp_node_t *pos;
	bb_t *ele;
	list_for_each_entry(pos, worklist, entry) {
		ele = (bb_t *)pos->addr;
		if(ele == bb) // 已经在工作表中
			return;
	}
	gp_node_add_tail(bb, worklist);
}


// 条件常量传播
void cond_const_prpgt_analyse(const_prpgt_info_t *cst_prpgt)
{
	int size = sizeof(double) * cst_prpgt->cnt;
	struct list_head *head = &cst_prpgt->dfg->bbs_head;
	bb_t *entry_block = container_of(head->next, bb_t, entry_in_dfg);
	memcpy(entry_block->const_prpgt.out_set, cst_prpgt->bound_vals, size);
	
	bb_t *pos = entry_block; // 初始化其他基本块 B.out  = UNDEF;
	list_for_each_entry_continue(pos, head, entry_in_dfg){ // 从当前节点的下一个
		memcpy(pos->const_prpgt.out_set, cst_prpgt->init_vals, size); 
	}

	LIST_HEAD(worklist);

	gp_node_t *node;
	list_for_each_entry(node, &entry_block->suc_head, entry) {
		bb_t *suc = node->addr;
		// 把 Entry 的每个后继加入工作表
		add_block_to_worklist(suc, &worklist); 
	}

	while(!list_empty(&worklist)) {
		struct list_head *first  = worklist.next;
		list_del(first);
		gp_node_t *node = container_of(first, gp_node_t, entry);
		bb_t *bb = (bb_t *)node->addr;
		free(node);

		block_join(bb);  // 交汇运算
		if(block_translate(bb)) { // out 有变化
			kill_cond_jmp(bb, head); // 不可达代码消除
			gp_node_t *pos;
			list_for_each_entry(pos, &bb->suc_head, entry) {
				bb_t *suc = pos->addr;
				// 把每个后继加入工作表
				add_block_to_worklist(suc, &worklist); 
			}
		}
	}
}

// 简单常量传播
void simple_const_prpgt_analyse(const_prpgt_info_t *cst_prpgt)
{
	int size = sizeof(double) * cst_prpgt->cnt;
	struct list_head *head = &cst_prpgt->dfg->bbs_head;
	bb_t *entry_block = container_of(head->next, bb_t, entry_in_dfg);
	// 初始化 Entry.out 为收集到的边界值
	memcpy(entry_block->const_prpgt.out_set, 
			cst_prpgt->bound_vals, size);

	// 初始化其他基本块 B.out  = UNDEF;
	bb_t *pos = entry_block;
	// 从当前节点的下一个
	list_for_each_entry_continue(pos, head, entry_in_dfg){ 
		memcpy(pos->const_prpgt.out_set, cst_prpgt->init_vals, size); 
	}

	int change = 1;	
	int loop = 1;
	while(change){
		change = 0;
		printf("loop = %d\n", loop++);
		pos = entry_block;
		// 从当前节点的下一个
		list_for_each_entry_continue(pos, head, entry_in_dfg) { 
			block_join(pos);  // 交汇运算
			 // 传递函数里面比较两次迭代out集合是否一致
			if(block_translate(pos)) 
				change = 1;			
		}
	}
}



bool __inst_algebra_simplify(inter_inst_t *inst)
{
	if(!inst)
		return false;

	operator_e op = inst->op;
	// 排除指令
	// IR_OP_DECL, IR_OP_FUN_ENTRY, IR_OP_FUN_EXIT
	// IR_OP_LOAD, IR_OP_STORE, IR_OP_LEA, 各种跳转, 
	// IR_OP_PROC, IR_OP_CALL, IR_OP_RET

	if(op < IR_OP_ASSIGN) // 只关心特定的表达式
		return false;
	if(op >= IR_OP_LOAD && op != IR_OP_ARG && op != IR_OP_RET_VAL)
		return false;

	if(op == IR_OP_ARG || op == IR_OP_RET_VAL) {
		if(!inst->arg1->is_literal){ // 参数或者返回值是变量
			double res = inst->out_set[inst->arg1->optimize_id];
			if(IS_CONST(res)){ 
				int tmp = (int)res;
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
				printf("在指令：");
				inter_inst_to_string(inst);
				printf("%s 是常量 %d, 替换为：\n", inst->arg1->name, tmp);
				printf("\n");
#endif
				var_t *new_var = new_literal(&tmp, NUM, -1);
				add_literal(new_var); // 添加到符号表
				inst->arg1 = new_var; //替换成常量操作数	
#ifdef ALGEBRA_SIMPLIFY_OUTPUT					
				inter_inst_to_string(inst);
#endif
				return true;				
			}		
		}
		return false;
	}

	var_t *res = inst->result;
	// 在输出集合中查结果
	double out_res = inst->out_set[res->optimize_id]; 
	if(IS_CONST(out_res) ) { // 结果为常量，替换为 result = c 指令
		if(op == IR_OP_ASSIGN && inst->arg1->is_literal)
			return false; // 本来就是 result = c 指令，无需替换

		int val = (int)out_res;
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
		printf("在指令(op = %d)", inst->op);
		inter_inst_to_string(inst);
		printf("%s 是常量 %d, 替换为：\n", inst->result->name, val);

#endif
		var_t *new = new_literal(&val, NUM, -1);
		add_literal(new); // 添加到符号表
		replace_inst(inst, IR_OP_ASSIGN, res, new, NULL);	
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
		printf("(new op = %d)", inst->op);
		inter_inst_to_string(inst);
		printf("\n");
#endif
		return true;
	} 

	if(op == IR_OP_ASSIGN || op == IR_OP_NOT || op == IR_OP_NEG)
		return false; // 这三种操作,无法继续化简,因为操作数不是常量

	var_t *arg1 = inst->arg1;
	var_t *arg2 = inst->arg2;
	double lval, rval; // 左右操作数
	lval = get_lattice(arg1, inst->in_set);
	rval = get_lattice(arg2, inst->in_set);	
	int left, right; // 记录常量值
	// 左右都是常量 inst_translate() 已经处理过了
	bool l_const = false, r_const = false; // 哪个操作数是常量
	if(IS_CONST(lval)){
		left = (int)lval; // 类型转换
		l_const = true;
	} else if(IS_CONST(rval)){
		right = rval; // 类型转换
		r_const = true;
	} else {
		return false; // 都不是常量，不处理
	} 

	var_t* new_arg1 = NULL; // 化简后新的操作数1
	var_t* new_arg2 = NULL; // 化简后新的操作数2(可选)
	operator_e new_op = IR_OP_ASSIGN; // 化简成功后默认为赋值运算		
	switch(op) {
		case IR_OP_ADD: // res = 0 + y; res = x + 0;
			if(l_const && left == 0){ // 左操作数是 0
				new_arg1 = arg2;  // 得到右操作数
			} else if(r_const && right == 0){ // 右操作数是0
				new_arg1 = arg1;   // 得到左操作数
			}
			break;

		case IR_OP_SUB: // res = 0 - y; res = x - 0;
			if(l_const && left == 0){  // 左操作数是 0
				new_op = IR_OP_NEG;  
				new_arg1 = arg2;      // 得到右操作数
			} else if(r_const && right == 0){ // 右操作数是 0
				new_arg1 = arg1;   // 得到左操作数
			}
			break;

		case IR_OP_MUL:
		 	// res = 0 * y; res = x * 0;
			if(((l_const && (left == 0))) || ((r_const && (right == 0)))){
				new_arg1 = sym_tab_g.zero;
			} else if(l_const && left == 1) { // res = 1 * y; res = x * 1;
				new_arg1 = arg2; // 得到右操作数
			} else if(r_const && right == 1){
				new_arg1 = arg1;  // 得到左操作数
			}		
			break;
		case IR_OP_DIV: // res = 0 / y; res = x / 1;
			if(l_const && left == 0){
				new_arg1 = sym_tab_g.zero;
			} else if(r_const && right == 1){
				new_arg1 = arg1;
			}	
			break;	
		case IR_OP_MOD: // res = 0 % y;  res = x % 1;
			if(((l_const && (left == 0))) || ((r_const && (right == 1)))){
				new_arg1 = sym_tab_g.zero;
			}
			break;
		case IR_OP_AND:// res = 0 && y; res = x && 0; 
		    // 优先级：== 高于 && 高于 ||
			if((l_const && left == 0) || (r_const && right == 0)){
				new_arg1 = sym_tab_g.zero;
			} else if(l_const && left != 0){  // res = !0 && y					
				new_op = IR_OP_NEQU;          // res = (y != 0);
				new_arg1 = arg2;
				new_arg2 = sym_tab_g.zero;
			} else if(r_const && right != 0){ // res = x && !0
				new_op = IR_OP_NEQU;   		  // res = (x != 0);
				new_arg1 = arg1;
				new_arg2 = sym_tab_g.zero;							
			}
			break;
		case IR_OP_OR: // res = !0 || y; res = x || !0;
			if((l_const && (left != 0)) || (r_const && (right != 0))){
				new_arg1 = sym_tab_g.one;
			} else if(l_const && left == 0){ // res = 0 || y;					
				new_op = IR_OP_NEQU;  		 // res = (y != 0);
				new_arg1 = arg2;
				new_arg2 = sym_tab_g.zero;				
			} else if(r_const && right == 0){ // res = x || 0;
				new_op = IR_OP_NEQU;   		  // res = (x != 0);
				new_arg1 = arg1;
				new_arg2 = sym_tab_g.zero;	
			}
			break;


		default:  // 判等、比较运算
			break;
	}

	if(new_arg1){ // 代数化简成功
		replace_inst(inst, new_op, res, new_arg1, new_arg2);	
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
		printf("指令：");
		inter_inst_to_string(inst);
		printf("替换为：\n");
		inter_inst_to_string(inst);
		printf("\n");
#endif
		return true;
	} else { // 无法化简，正常传播
		if(arg1->is_literal || arg2->is_literal)
			return false; // 本来就是常量，不用替换
		if(l_const){ // 传播左操作数
			new_arg1 = new_literal(&left, NUM, -1);
			add_literal(new_arg1);
			// 替换左操作数为常量
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
			printf("指令：");
			inter_inst_to_string(inst);
			printf("替换为：\n");
#endif
			replace_inst(inst, op, res, new_arg1, arg2);	
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
			inter_inst_to_string(inst);
			printf("\n");
#endif			
			return true;
		} else if(r_const){ // 传播右操作数
			new_arg2 = new_literal(&right, NUM, -1);
			add_literal(new_arg2);
			// 替换右操作数为常量
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
			printf("指令：");
			inter_inst_to_string(inst);
			printf("替换为：\n");
#endif
			replace_inst(inst, op, res, arg1, new_arg2);	
#ifdef ALGEBRA_SIMPLIFY_OUTPUT
			inter_inst_to_string(inst);
			printf("\n");
#endif	
			return true;
		}
		return false;
	}
}


void print_set_name(const_prpgt_info_t *cst_prpgt)
{
	if(!cst_prpgt)
		return;
	for(int i = 0; i < cst_prpgt->cnt; ++i)
		printf("%s ",cst_prpgt->var_info[i]->name);
	printf("\n");
}
// 代数化简
// head:  中间指令链表的头节点
bool algebra_simplify(struct list_head *head)
{
	if(!head)
		return false;
	
	inter_inst_t *inst;
	operator_e op;
	bool change = false;
	list_for_each_entry(inst, head, entry) { 
		if(!inst->in_bb->reach)
			continue;

		if(__inst_algebra_simplify(inst))
			change = true;
	}
	return change;
}


void kill_cond_jmp(bb_t *bb, struct list_head *head)
{
	inter_inst_t *inst = container_of(bb->insts_head.prev, 
				inter_inst_t, entry_in_bb);
	if(inter_inst_is_cond_jmp(inst)) {
		operator_e op = inst->op;
		var_t *arg1 = inst->arg1;
		var_t *arg2 = inst->arg2;
		double cond = get_lattice(arg1, inst->in_set);
		if(NOT_CONST(cond))
			return;
		bb_t *next_bb = container_of(bb->entry_in_dfg.next, 
				bb_t, entry_in_dfg); // 求紧跟它的块
		if(((op == IR_OP_JT) && (cond == 0)) ||
				 ((op == IR_OP_JF) && (cond != 0))) { // 肯定不跳转
			if(inst->jmp_target->in_bb != next_bb) { // 目标块不是紧跟块
				// 删除指令所在块到目标块的边
				kill_link(bb, inst->jmp_target->in_bb, head); 
				return;
			}
		} else if(((op == IR_OP_JT) && (cond != 0)) || 
				((op == IR_OP_JF) && (cond == 0))) { // 肯定跳转
			if(inst->jmp_target->in_bb != next_bb) { // 目标块不是紧跟块
				kill_link(bb, next_bb, head); 
				return;
			}
		} else if(op == IR_OP_JE || op == IR_OP_JNE) {
			double val = get_lattice(arg2, inst->in_set);
			if(NOT_CONST(val))
				return;
			if((op == IR_OP_JNE && cond != val) || 
					(op == IR_OP_JE && cond == val)) {
				// 肯定跳转
				// 目标块不是紧跟块
				if(inst->jmp_target->in_bb != next_bb) { 
					kill_link(bb, next_bb, head); 
					return; 
				}
			} else if((op == IR_OP_JNE && cond == val) ||
					 (op == IR_OP_JE && cond != val)) {
				// 肯定不跳转
				// 目标块不是紧跟块
				if(inst->jmp_target->in_bb != next_bb) { 
					kill_link(bb, inst->jmp_target->in_bb, head);	
					return; 
				}
			}
		} 
	}	
}


// 	条件跳转优化，同时进行不可达代码消除
void cond_jmp_optimize(dfg_t *dfg)
{
	if(!dfg)
		return;
	struct list_head *head = &dfg->bbs_head;
	bb_t *bb, *next_bb; 
	inter_inst_t *inst, *next_inst;

	list_for_each_entry(bb, head, entry_in_dfg) { 	
		// 可能会有指令删除的操作，所以用安全遍历
		list_for_each_entry_safe(inst, next_inst, 
					 &bb->insts_head, entry_in_bb){
			if(inter_inst_is_cond_jmp(inst)){
				operator_e op = inst->op;
				var_t *arg1 = inst->arg1;
				var_t *arg2 = inst->arg2;
				double cond = get_lattice(arg1, inst->in_set);
				if(NOT_CONST(cond))
					continue; // 条件不是常量，无法优化
				// 因为增加了 exit 块，所以肯定存在紧跟它的块
				next_bb = container_of(bb->entry_in_dfg.next, 
						bb_t, entry_in_dfg); // 求紧跟它的块

				if(((op == IR_OP_JT) && (cond == 0)) || 
					((op == IR_OP_JF) && (cond != 0))) { // 肯定不跳转
#ifdef COND_JMP_OPTIMIZE_OUTPUT
					printf("删除指令:");
					inter_inst_to_string(inst);
#endif
					list_del(&inst->entry_in_bb);  // 将该指令从基本块内删除
					// 如果目标块是紧跟块，虽然把跳转指令删除了，但因为是顺序执行
					// 当前块的后继还是紧跟块，这个关系不能解除	
					
					if(inst->jmp_target->in_bb != next_bb) { // 目标块不是紧跟块
						// 删除指令所在块到目标块的边
						kill_link(bb, inst->jmp_target->in_bb, head); 
					} 
						
				} else if(((op == IR_OP_JT) && (cond != 0)) ||
						 ((op == IR_OP_JF) && (cond == 0))) { // 肯定跳转
#ifdef COND_JMP_OPTIMIZE_OUTPUT
					printf("把指令:");
					inter_inst_to_string(inst);
					printf("替换成无条件跳转\n");
#endif
					inst->op = IR_OP_JMP; // 替换成无条件跳转指令
					if(inst->jmp_target->in_bb != next_bb) //  目标块不是紧跟块
						kill_link(bb, next_bb, head); // 删除指令所在块到紧跟块的边
				} 
				else if(op == IR_OP_JE) { // arg1 和 arg2 都是常量才能优化
					double val = get_lattice(arg2, inst->in_set);
					if(IS_CONST(val)) {
						if(cond == val) { // 肯定跳转
							inst->op = IR_OP_JMP; // 替换成无条件跳转指令
#ifdef COND_JMP_OPTIMIZE_OUTPUT
							printf("把指令:");
							inter_inst_to_string(inst);
							printf("替换成无条件跳转\n");
#endif
							if(inst->jmp_target->in_bb != next_bb) //  目标块不是紧跟块
								kill_link(bb, next_bb, head); //  删除指令所在块到紧跟块的边
						} else { // 肯定不跳转
#ifdef COND_JMP_OPTIMIZE_OUTPUT
							printf("删除指令:");
							inter_inst_to_string(inst);
#endif
							list_del(&inst->entry_in_bb);  // 将该指令从基本块内删除		
							if(inst->jmp_target->in_bb != next_bb) // 目标块不是紧跟块
							 	//  删除指令所在块到目标块的边
								kill_link(bb, inst->jmp_target->in_bb, head);
						}						
					}
				} else if(op == IR_OP_JNE) {
					double val = get_lattice(arg2, inst->in_set);
					if(IS_CONST(val)) {
						if(cond != val) { // 肯定跳转
							inst->op = IR_OP_JMP; // 替换成无条件跳转指令
#ifdef COND_JMP_OPTIMIZE_OUTPUT
							printf("把指令:");
							inter_inst_to_string(inst);
							printf("替换成无条件跳转\n");
#endif
							if(inst->jmp_target->in_bb != next_bb) //  目标块不是紧跟块
								kill_link(bb, next_bb, head); //  删除指令所在块到紧跟块的边
						} else { // 肯定不跳转
#ifdef COND_JMP_OPTIMIZE_OUTPUT
							printf("删除指令:");
							inter_inst_to_string(inst);
#endif							
							list_del(&inst->entry_in_bb);  // 将该指令从基本块内删除		
							if(inst->jmp_target->in_bb != next_bb) // 目标块不是紧跟块
								// 删除指令所在块到目标块的边	
								kill_link(bb, inst->jmp_target->in_bb, head); 
						}
					}
				}	
			}	
		}
	}
}
	

void optimize_simple_const_prpgt(fun_t *fun)
{
	const_prpgt_info_t *cst_prpgt = const_prpgt_init(fun);
	if(!cst_prpgt)
		return;
	print_set_name(cst_prpgt);
	int change = 1;
	int loop = 1;
	while(change){ // 循环做是为了达到更好的优化效果
		change = 0;
		printf("simple_const_prpgt_analyse --- %d\n", loop++);
		simple_const_prpgt_analyse(cst_prpgt);
		if(algebra_simplify(cst_prpgt->inter_code))
			change = 1;
		cond_jmp_optimize(cst_prpgt->dfg);
		if(remove_unreachable_block(&cst_prpgt->dfg->bbs_head)) {
			change = 1;
		}
	}
	extract_reachable_code(&cst_prpgt->dfg->bbs_head, &cst_prpgt->optimized_code);
	printf("简单常量传播优化结果：\n");
	print_optimized_code(&cst_prpgt->optimized_code);	
	const_prpgt_destroy(cst_prpgt);
}



void optimize_cond_const_prpgt(fun_t *fun)
{
	const_prpgt_info_t *cst_prpgt = const_prpgt_init(fun);
	if(!cst_prpgt)
		return;

	cond_const_prpgt_analyse(cst_prpgt);
	remove_unreachable_block(&cst_prpgt->dfg->bbs_head);
	algebra_simplify(cst_prpgt->inter_code);
	cond_jmp_optimize(cst_prpgt->dfg);
	extract_reachable_code(&cst_prpgt->dfg->bbs_head, &cst_prpgt->optimized_code);
	printf("条件常量传播优化结果：\n");
	print_optimized_code(&cst_prpgt->optimized_code);	
	const_prpgt_destroy(cst_prpgt);
}


void optimize_funs(void)
{
  	fun_t *fun;
	unsigned bkt;
	hash_for_each(sym_tab_g.fun_tab, bkt, fun, hnode) {
        if(fun->is_ext)
            continue;
        create_dfg(fun);
        print_dfg_dot(fun);
		optimize_cond_const_prpgt(fun);
	}	
}